SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Finitary relation</title>

</head>

Finitary relation

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, a finitary relation over a sequence of sets X1, ..., Xn is a <a href="Subset" title="Subset">subset</a> of the <a href="Cartesian_product" title="Cartesian product">Cartesian product</a> X1 × ... × Xn; that is, it is a set of n-tuples (x1, ..., xn), each being a sequence of elements xi in the corresponding Xi.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a><a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.

The non-negative integer n that gives the number of "places" in the relation is called the <a href="Arity" title="Arity">arity</a>, adicity or degree of the relation. A relation with n "places" is variously called an n-ary relation, an n-adic relation or a relation of degree n. Relations with a finite number of places are called finitary relations (or simply relations if the context is clear). It is also possible to generalize the concept to infinitary relations with <a href="Sequence" title="Sequence">infinite sequences</a>.<a href="#cite_note-FOOTNOTENivat1981-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">When two objects, qualities, classes, or attributes, viewed together by the mind, are seen under some connexion, that connexion is called a relation.</blockquote><div class="templatequotecite">— <a href="Augustus_De_Morgan" title="Augustus De Morgan">Augustus De Morgan</a><a href="#cite_note-FOOTNOTEDe_Morgan1966-5">[5]</a></div>

<dl><dt>Definition</dt>

<dd>R is an n-ary relation on sets X1, ..., Xn is given by a subset of the Cartesian product X1 × ... × Xn.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a></dd></dl>

Since the definition is predicated on the underlying sets X1, ..., Xn, R may be more formally defined as the (n + 1)-tuple (X1, ..., Xn, G), where G, called the graph of R, is a subset of the Cartesian product X1 × ... × Xn.

As is often done in mathematics, the same symbol is used to refer to the mathematical object and an underlying set, so the statement (x1, ..., xn) ∈ R is often used to mean (x1, ..., xn) ∈ G is read "x1, ..., xn are R-related" and are denoted using <a href="Polish_notation" title="Polish notation">prefix notation</a> by Rx1⋯xn and using <a href="Reverse_Polish_notation" title="Reverse Polish notation">postfix notation</a> by x1⋯xnR. In the case where R is a binary relation, those statements are also denoted using <a href="Infix_notation" title="Infix notation">infix notation</a> by x1Rx2.

The following considerations apply:

<ul><li>The set Xi is called the ith domain of R.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a> In the case where R is a binary relation, X1 is also called simply the <a href="Binary_relation#Definition" title="Binary relation">domain</a> or set of departure of R, and X2 is also called the <a href="Binary_relation#Definition" title="Binary relation">codomain</a> or set of destination of R.</li>

<li>When the elements of Xi are relations, Xi is called a nonsimple domain of R.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a></li>

<li>The set of ∀xi ∈ Xi such that Rx1⋯xi−1xixi+1⋯xn for at least one (x1, ..., xn) is called the ith domain of definition or active domain of R.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a> In the case where R is a binary relation, its first domain of definition is also called simply the <a href="Binary_relation#Definition" title="Binary relation">domain of definition</a> or active domain of R, and its second domain of definition is also called the <a href="Binary_relation#Definition" title="Binary relation">codomain of definition</a> or active codomain of R.</li>

<li>When the ith domain of definition of R is equal to Xi, R is said to be total on its ith domain (or on Xi, when this is not ambiguous). In the case where R is a binary relation, when R is total on X1, it is also said to be <a href="Binary_relation#Special_types_of_binary_relations" title="Binary relation">left-total</a> or serial, and when R is total on X2, it is also said to be <a href="Binary_relation#Special_types_of_binary_relations" title="Binary relation">right-total</a> or surjective.</li>

<li>When ∀x ∀y ∈ Xi. ∀z ∈ Xj. xRijz ∧ yRijz ⇒ x = y, where i ∈ I, j ∈ J, Rij = πij R, and {I, J} is a <a href="Partition_of_a_set" title="Partition of a set">partition</a> of {1, ..., n}, R is said to be unique on {Xi}i∈I, and {Xi}i∈J is called a <a href="Primary_key" title="Primary key">primary key</a><a href="#cite_note-FOOTNOTECodd1970-1">[1]</a> of R. In the case where R is a binary relation, when R is unique on {X1}, it is also said to be <a href="Binary_relation#Special_types_of_binary_relations" title="Binary relation">left-unique</a> or injective, and when R is unique on {X2}, it is also said to be <a href="Binary_relation#Special_types_of_binary_relations" title="Binary relation">univalent</a> or right-unique.</li>

<li>When all Xi are the same set X, it is simpler to refer to R as an n-ary relation over X, called a <a href="Homogeneous_relation" title="Homogeneous relation">homogeneous relation</a>. Without this restriction, R is called a <a href="Heterogeneous_relation" class="mw-redirect" title="Heterogeneous relation">heterogeneous relation</a>.</li>

<li>When any of Xi is empty, the defining Cartesian product is empty, and the only relation over such a sequence of domains is the empty relation R = ∅.</li></ul>

Let a <a href="Boolean_domain" title="Boolean domain">Boolean domain</a> B be a two-element set, say, B = {0, 1}, whose elements can be interpreted as logical values, typically 0 = false and 1 = true. The <a href="Indicator_function" title="Indicator function">characteristic function</a> of R, denoted by χR, is the <a href="Boolean-valued_function" title="Boolean-valued function">Boolean-valued function</a> χR: X1 × ... × Xn → B, defined by χR((x1, ..., xn)) = 1 if Rx1⋯xn and χR((x1, ..., xn)) = 0 otherwise.

In applied mathematics, <a href="Computer_science" title="Computer science">computer science</a> and statistics, it is common to refer to a Boolean-valued function as an n-ary <a href="Predicate_(mathematics)" class="mw-redirect" title="Predicate (mathematics)">predicate</a>. From the more abstract viewpoint of <a href="Formal_logic" class="mw-redirect" title="Formal logic">formal logic</a> and <a href="Model_theory" title="Model theory">model theory</a>, the relation R constitutes a logical model or a relational structure, that serves as one of many possible <a href="Interpretation_(logic)" title="Interpretation (logic)">interpretations</a> of some n-ary predicate symbol.

Because relations arise in many scientific disciplines, as well as in many branches of <a href="Mathematics" title="Mathematics">mathematics</a> and <a href="Logic" title="Logic">logic</a>, there is considerable variation in terminology. Aside from the <a href="Set_theory" title="Set theory">set-theoretic</a> <a href="Extension_(semantics)" title="Extension (semantics)">extension</a> of a relational concept or term, the term "relation" can also be used to refer to the corresponding logical entity, either the <a href="Comprehension_(logic)" title="Comprehension (logic)">logical comprehension</a>, which is the totality of <a href="Intension" title="Intension">intensions</a> or abstract properties shared by all elements in the relation, or else the symbols denoting these elements and intensions. Further, some writers of the latter persuasion introduce terms with more concrete connotations (such as "relational structure" for the set-theoretic extension of a given relational concept).

<div class="mw-heading mw-heading2"><h2 id="Specific_values_of_n">Specific values of n</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Nullary">Nullary</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Relation_of_degree_zero" title="Relation of degree zero">Relation of degree zero</a></div>

Nullary (0-ary) relations count only two members: the empty nullary relation, which never holds, and the universal nullary relation, which always holds. This is because there is only one 0-tuple, the empty tuple (), and there are exactly two subsets of the (singleton) set of all 0-tuples. They are sometimes useful for constructing the base case of an <a href="Mathematical_induction" title="Mathematical induction">induction</a> argument.

<div class="mw-heading mw-heading3"><h3 id="Unary">Unary</h3></div>

Unary (1-ary) relations can be viewed as a collection of members (such as the collection of <a href="Nobel_laureates" class="mw-redirect" title="Nobel laureates">Nobel laureates</a>) having some property (such as that of having been awarded the <a href="Nobel_Prize" title="Nobel Prize">Nobel Prize</a>).

Every nullary function is a unary relation.

<div class="mw-heading mw-heading3"><h3 id="Binary">Binary</h3></div>

<a href="Binary_relation" title="Binary relation">Binary</a> (2-ary) relations are the most commonly studied form of finitary relations. Homogeneous binary relations (where X1 = X2) include

<ul><li><a href="Equality_(mathematics)" title="Equality (mathematics)">Equality</a> and <a href="Inequality_(mathematics)" title="Inequality (mathematics)">inequality</a>, denoted by signs such as = and < in statements such as "5 < 12", or</li>

<li><a href="Divisor" title="Divisor">Divisibility</a>, denoted by the sign | in statements such as "13 | 143".</li></ul>

Heterogeneous binary relations include

<ul><li><a href="Element_(mathematics)" title="Element (mathematics)">Set membership</a>, denoted by the sign ∈ in statements such as "1 ∈ N".</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Ternary">Ternary</h3></div>

<a href="Ternary_relation" title="Ternary relation">Ternary</a> (3-ary) relations include, for example, the <a href="Binary_function" title="Binary function">binary functions</a>, which relate two inputs and the output. All three of the domains of a homogeneous ternary relation are the same set.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Consider the ternary relation R "x thinks that y likes z" over the set of people P = { Alice, Bob, Charles, Denise }, defined by:

<dl><dd>R = { (Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise) }.</dd></dl>

R can be represented equivalently by the following table:

<caption>Relation R "x thinks that y likes z"

</caption>

<th>z

</th></tr>

<tr>

<td>Alice</td>

<td>Denise

</td></tr>

<tr>

<td>Charles</td>

<td>Alice</td>

<td>Bob

</td></tr>

<tr>

<td>Charles</td>

<td>Alice

</td></tr>

<tr>

<td>Denise</td>

<td>Denise

</td></tr></tbody></table>

Here, each row represents a triple of R, that is it makes a statement of the form "x thinks that y likes z". For instance, the first row states that "Alice thinks that Bob likes Denise". All rows are distinct. The ordering of rows is insignificant but the ordering of columns is significant.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a>

The above table is also a simple example of a <a href="Relational_database" title="Relational database">relational database</a>, a field with theory rooted in <a href="Relational_algebra" title="Relational algebra">relational algebra</a> and applications in data management.<a href="#cite_note-6">[6]</a> Computer scientists, logicians, and mathematicians, however, tend to have different conceptions what a general relation is, and what it is consisted of. For example, databases are designed to deal with empirical data, which is by definition finite, whereas in mathematics, relations with infinite arity (i.e., infinitary relation) are also considered.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Algebraic_logic#History" title="Algebraic logic">Algebraic logic § History</a></div>

The logician <a href="Augustus_De_Morgan" title="Augustus De Morgan">Augustus De Morgan</a>, in work published around 1860, was the first to articulate the notion of relation in anything like its present sense. He also stated the first formal results in the theory of relations (on De Morgan and relations, see Merrill 1990).

<a href="Charles_Sanders_Peirce" title="Charles Sanders Peirce">Charles Peirce</a>, <a href="Gottlob_Frege" title="Gottlob Frege">Gottlob Frege</a>, <a href="Georg_Cantor" title="Georg Cantor">Georg Cantor</a>, <a href="Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a> and others advanced the theory of relations. Many of their ideas, especially on relations called <a href="Order_theory" title="Order theory">orders</a>, were summarized in <a href="The_Principles_of_Mathematics" title="The Principles of Mathematics">The Principles of Mathematics</a> (1903) where <a href="Bertrand_Russell" title="Bertrand Russell">Bertrand Russell</a> made free use of these results.

In 1970, <a href="Edgar_F._Codd" title="Edgar F. Codd">Edgar Codd</a> proposed a <a href="Relational_model" title="Relational model">relational model</a> for <a href="Database" title="Database">databases</a>, thus anticipating the development of <a href="Data_base_management_system" class="mw-redirect" title="Data base management system">data base management systems</a>.<a href="#cite_note-FOOTNOTECodd1970-1">[1]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 22em;">

<ul><li><a href="Incidence_structure" title="Incidence structure">Incidence structure</a></li>

<li><a href="Hypergraph" title="Hypergraph">Hypergraph</a></li>

<li><a href="Logic_of_relatives" class="mw-redirect" title="Logic of relatives">Logic of relatives</a></li>

<li><a href="Logical_matrix" title="Logical matrix">Logical matrix</a></li>

<li><a href="Partial_order" class="mw-redirect" title="Partial order">Partial order</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate (mathematical logic)</a></li>

<li><a href="Projection_(set_theory)" title="Projection (set theory)">Projection (set theory)</a></li>

<li><a href="Reflexive_relation" title="Reflexive relation">Reflexive relation</a></li>

<li><a href="Relation_algebra" title="Relation algebra">Relation algebra</a></li>

<li><a href="Relational_algebra" title="Relational algebra">Relational algebra</a></li>

<li><a href="Relational_model" title="Relational model">Relational model</a></li>

<li><a href="Relations_(philosophy)" class="mw-redirect" title="Relations (philosophy)">Relations (philosophy)</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php/Relation">"Relation – Encyclopedia of Mathematics"</a>. www.encyclopediaofmath.org. Retrieved 2019-12-12.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.cs.odu.edu/~toida/nerzic/content/relation/definition/cp_gen/index.html">"Definition of n-ary Relation"</a>. cs.odu.edu. Retrieved 2019-12-12.</cite>

</li>

<li id="cite_note-FOOTNOTENivat1981-4"><a href="#cite_ref-FOOTNOTENivat1981_4-0">^</a> <a href="#CITEREFNivat1981">Nivat 1981</a>

</li>

<li id="cite_note-FOOTNOTEDe_Morgan1966-5"><a href="#cite_ref-FOOTNOTEDe_Morgan1966_5-0">^</a> <a href="#CITEREFDe_Morgan1966">De Morgan 1966</a>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.pitt.edu/~bonidie/cs441/relations.pdf">"Relations – CS441"</a> (PDF). www.pitt.edu. Retrieved 2019-12-11.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFBourbaki1994" class="citation cs2"><a href="Nicolas_Bourbaki" title="Nicolas Bourbaki">Bourbaki, N.</a> (1994), Elements of the History of Mathematics, translated by <a href="John_D._P._Meldrum" title="John D. P. Meldrum">John Meldrum</a>, Springer-Verlag</cite></li>

<li><cite id="CITEREFCarnap1958" class="citation cs2"><a href="Rudolf_Carnap" title="Rudolf Carnap">Carnap, Rudolf</a> (1958), Introduction to Symbolic Logic with Applications, Dover Publications</cite></li>

<li><cite id="CITEREFCodd1970" class="citation journal cs1"><a href="Edgar_F._Codd" title="Edgar F. Codd">Codd, Edgar Frank</a> (June 1970). <a rel="nofollow" class="external text" href="https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf">"A Relational Model of Data for Large Shared Data Banks"</a> (PDF). Communications of the ACM. 13 (6): 377–387. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F362384.362685">10.1145/362384.362685</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207549016">207549016</a>. Retrieved 2020-04-29.</cite></li>

<li><cite id="CITEREFCodd1990" class="citation book cs1"><a href="Edgar_F._Codd" title="Edgar F. Codd">Codd, Edgar Frank</a> (1990). <a rel="nofollow" class="external text" href="https://codeblab.com/wp-content/uploads/2009/12/rmdb-codd.pdf">The Relational Model for Database Management: Version 2</a> (PDF). Boston: <a href="Addison-Wesley" title="Addison-Wesley">Addison-Wesley</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0201141924</bdi>.</cite></li>

<li><cite id="CITEREFDe_Morgan1966" class="citation cs2"><a href="Augustus_De_Morgan" title="Augustus De Morgan">De Morgan, A.</a> (1966) [1858], "On the syllogism, part 3", in Heath, P. (ed.), On the syllogism and other logical writings, Routledge, p. 119</cite></li>

<li><cite id="CITEREFHalmos1960" class="citation cs2"><a href="Paul_Richard_Halmos" class="mw-redirect" title="Paul Richard Halmos">Halmos, P.R.</a> (1960), Naive Set Theory, Princeton NJ: D. Van Nostrand Company</cite></li>

<li><cite id="CITEREFLawvereRosebrugh2003" class="citation cs2"><a href="William_Lawvere" title="William Lawvere">Lawvere, F.W.</a>; Rosebrugh, R (2003), Sets for Mathematics, Cambridge Univ. Press</cite></li>

<li><a href="Clarence_Irving_Lewis" class="mw-redirect" title="Clarence Irving Lewis">Lewis, C.I.</a> (1918) <a href="https://archive.org/details/asurveyofsymboli00lewiuoft" class="extiw external" title="iarchive:asurveyofsymboli00lewiuoft">A Survey of Symbolic Logic</a>, Chapter 3: Applications of the Boole–Schröder Algebra, via <a href="Internet_Archive" title="Internet Archive">Internet Archive</a></li>

<li><cite id="CITEREFLucas1999" class="citation cs2"><a href="John_Lucas_(philosopher)" title="John Lucas (philosopher)">Lucas, J.R.</a> (1999), Conceptual Roots of Mathematics, Routledge</cite></li>

<li><cite id="CITEREFMaddux2006" class="citation cs2"><a href="Roger_Maddux" title="Roger Maddux">Maddux, R.D.</a> (2006), Relation Algebras, Studies in Logic and the Foundations of Mathematics, vol. 150, Elsevier Science</cite></li>

<li><cite id="CITEREFMerrill1990" class="citation cs2">Merrill, Dan D. (1990), Augustus De Morgan and the logic of relations, Kluwer</cite></li>

<li><cite id="CITEREFNivat1981" class="citation book cs1"><a href="Maurice_Nivat" title="Maurice Nivat">Nivat, M.</a> (1981). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/3-540-10828-9_54">"Infinitary relations"</a>. In Astesiano, Egidio; Böhm, Corrado (eds.). Caap '81. Lecture Notes in Computer Science. Vol. 112. Springer Berlin Heidelberg. pp. 46–75. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-10828-9_54">10.1007/3-540-10828-9_54</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-38716-9</bdi>.</cite></li>

<li><a href="Charles_Sanders_Peirce" title="Charles Sanders Peirce">Peirce, C.S.</a> (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memoirs of the American Academy of Arts and Sciences 9, 317–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.</li>

<li><a href="Charles_Sanders_Peirce" title="Charles Sanders Peirce">Peirce, C.S.</a> (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867–1871. Peirce Edition Project, eds. Indiana University Press.</li>

<li><cite id="CITEREFRussell1938" class="citation cs2"><a href="Bertrand_Russell" title="Bertrand Russell">Russell, B.</a> (1938) [1903], <a rel="nofollow" class="external text" href="http://fair-use.org/bertrand-russell/the-principles-of-mathematics">The Principles of Mathematics</a> (2nd ed.), Cambridge Univ. Press.</cite></li>

<li><cite id="CITEREFSuppes1972" class="citation cs2"><a href="Patrick_Suppes" title="Patrick Suppes">Suppes, P.</a> (1972) [1960], Axiomatic Set Theory, Dover Publications</cite></li>

<li><cite id="CITEREFTarski1983" class="citation cs2"><a href="Alfred_Tarski" title="Alfred Tarski">Tarski, A.</a> (1983) [1956], Logic, Semantics, Metamathematics, Papers from 1923 to 1938, translated by J.H. Woodger (1st ed.), Oxford University Press</cite> 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.</li>

<li><a href="Stanislaw_Ulam" class="mw-redirect" title="Stanislaw Ulam">Ulam, S.M.</a> and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press, Berkeley, CA.</li>

<li><cite id="CITEREFUlam1990" class="citation cs2"><a href="Stanislaw_Ulam" class="mw-redirect" title="Stanislaw Ulam">Ulam, S.M.</a> (1990), A.R. Bednarek; Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press</cite></li>

<li><cite id="CITEREFFraïssé2000" class="citation cs2"><a href="Roland_Fra%C3%AFss%C3%A9" title="Roland Fraïssé">Fraïssé, R.</a> (2000) [1986], Theory of Relations, North Holland</cite></li></ul>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)  and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Boolean_function" title="Boolean function">Boolean functions</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>/<a href="Surjective_function" title="Surjective function">Sur</a>/<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems">list</a>), <a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic systems</a> (<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements">Elements</a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_function" title="Computable function">Computable function</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4177675-6">Germany</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-09" href="https://en.wikipedia.org/wiki/?title=Finitary_relation&oldid=1268379078">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>